package org.ww.algorithm.avl;

import java.util.Arrays;

public class AVLTreeDemo {
    public static void main(String[] args) {
//        int[] arr={4,3,6,5,7,8};
//        int[] arr={10,12,8,9,7,2};
        int[] arr={10,11,7,6,8,9};
        AVLTree avlTree=new AVLTree();
        for(int i=0;i<arr.length;i++){
            avlTree.add(new BinaryNode(arr[i]));
        }

        System.out.println("中序遍历后");
        avlTree.indexOrder();
        System.out.println("平衡处理后~");
        System.out.println("树的高度："+avlTree.getRoot().getHeight());
        System.out.println("树的左子树高度"+avlTree.getRoot().getLeftHeight());
        System.out.println("树的右子树高度"+avlTree.getRoot().getRightHeight());
    }
}
class AVLTree{
    BinaryNode root;
    public BinaryNode getRoot(){
        return root;
    }

    public void add(BinaryNode node){
        if(root!=null){
            root.addNode(node);
        }else{
            root=node;
        }
    }
    //查找目标节点
    public BinaryNode search(int value){
        if(root==null){
            return null;
        }else{
            return root.search(value);
        }
    }

    //查找目标节点的父节点
    public BinaryNode searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

    /**
     * 查找根节点最小的节点值，返回并删除
     * @param node
     * @return
     */
    public BinaryNode delRightMin(BinaryNode node){
        BinaryNode target=node;
        while(target.left!=null){
            target=target.left;
        }
        delete(target.value);
        return target;
    }
    //删除节点
    public void delete(int value){
        if(root==null){
            return ;
        }else{
            //查找目标节点
            BinaryNode targetNode = search(value);
            if(targetNode==null){
                return ;
            }
            //删除的是根节点
            if(root.left==null && root.right==null){
                root=null;
                return ;
            }
            //查找目标节点的父节点
            BinaryNode parentNode = searchParent(value);
            //1 删除的是叶子节点
            if(targetNode.left==null && targetNode.right==null){
                if(parentNode.left!=null && parentNode.left.value==value ){
                    parentNode.left=null;
                }else if( parentNode.right!=null && parentNode.right.value==value ){
                    parentNode.right=null;
                }
            }else if(targetNode.left!=null && targetNode.right!=null){
                //2 删除有两个子节点的树
                BinaryNode binaryNode = delRightMin(targetNode.right);
                targetNode.value=binaryNode.value;
            }else {

                //3 删除只有一个子节点的树
                if(targetNode.left!=null){
                    if(parentNode!=null){
                        if(parentNode.left.value==value){
                            parentNode.left=targetNode.left;
                        }else{
                            parentNode.right=targetNode.left;
                        }
                    }else {
                        root=targetNode.left;
                    }

                }else{
                    if(parentNode==null){
                        if(parentNode.left.value==value){
                            parentNode.left=targetNode.right;
                        }else{
                            parentNode.right=targetNode.right;
                        }
                    }else{
                        root=targetNode.right;
                    }
                }
            }
        }
    }

    public void indexOrder(){
        root.infixOrder();
    }
}
class BinaryNode{
    int value;
    BinaryNode left;
    BinaryNode right;

    public BinaryNode(int value) {
        this.value = value;
    }
    //左旋转
    public void leftRotate(){

        BinaryNode newNode = new BinaryNode(value);
        newNode.left=left;
        newNode.right=right.left;

        //修改当前根节点的值
        value=right.value;

        right=right.right;
        left=newNode;

    }

    //右旋转
    public void rightRotate(){
        BinaryNode newNode = new BinaryNode(value);

        newNode.right=right;
        newNode.left=left.right;

        value=left.value;
        left=left.left;
        right=newNode;
    }

    //获取左子树高度
    public int getLeftHeight(){
        if(left==null)
            return 0;
        return left.getHeight();
    }
    //获取右子树高度
    public int getRightHeight(){
        if(right==null)
            return 0;
        return right.getHeight();
    }
    //获取当前节点的高度
    public int getHeight(){
        return Math.max(this.left==null?0:this.left.getHeight(),this.right==null?0:this.right.getHeight())+1;
    }
    //查找要删除的目标节点
    public BinaryNode search(int value){
        if(this.value==value){
            return this;
        }else if(value < this.value){
            if(this.left==null){
                return null;
            }
            return this.left.search(value);
        }else{
            if(this.right==null){
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找要删除节点的父节点
    public BinaryNode searchParent(int value){
        if((this.left!=null && this.left.value == value ) ||
                (this.right!=null && this.right.value==value )){
            return this;
        }else{
            if( this.left!=null && value<this.value ){
                return this.left.searchParent(value);
            }else if( this.right!=null && value>=this.value ){
                return this.right.searchParent(value);
            }else{
                return null;
            }
        }
    }


    //添加节点
    public void addNode(BinaryNode node){
        if(node==null){
            return;
        }
        if(node.value<this.value){
            if(this.left==null){
                this.left=node;
            }else{
                this.left.addNode(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.addNode(node);
            }
        }
        //当添加完一个节点的值以后，判断左右子树的高度的差是否大于1
        if(getRightHeight()-getLeftHeight()>1){
            //如果右子树的左子树高度大于右子树高度，则先对该右子树进行右旋转
            if(right!=null && right.getLeftHeight()>right.getRightHeight()){
                right.rightRotate();
                leftRotate();
            }else{
                leftRotate();
            }
            return ;  //有必要
        }

        if(getLeftHeight()-getRightHeight()>1){
            //如果左子树的右子树高度大于左子树的高度，则先对左子树进行左旋转
            if(left!=null && left.getRightHeight()>left.getLeftHeight()){
                left.leftRotate();
                rightRotate();
            }else{
                rightRotate();
            }
        }
    }

    //中序遍历
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }



    @Override
    public String toString() {
        return "BinaryNode{" +
                "value=" + value +
                '}';
    }
}
